package lineartable.linkedlist.doublylinkedlist.doublycirculardemo;

import java.util.Scanner;
public class DoubleLinkedList<AnyType>{
    //定义双向链表节点
    private class Node<AnyType>{
        AnyType data;
        Node<AnyType> next;
        Node<AnyType> prev;
        //构造函数
        private Node()
        {
            data=null;
            prev=null;
            next=null;
        }
        private Node(AnyType data){
            this.data=data;
            this.prev=null;
            this.next=null;
        }
        private Node(AnyType data,Node<AnyType> prev,Node<AnyType> next){
            this.data=data;
            this.prev=prev;
            this.next=next;
        }
    }
    private int size=0;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;

    //初始化一个空的双向循环链表
    public DoubleLinkedList(){
        beginMarker=new Node<AnyType>();
        endMarker=new Node<AnyType>();
        //key point
        beginMarker.prev=endMarker;
        beginMarker.next=null;
        endMarker.prev=null;
        //together
        endMarker.next=beginMarker;
    }
    public void init(){
        System.out.println("双向循环链表的操作：");
        System.out.println("1.空的双向循环链表已经建立");
    }
    //2.用于向空的双向循环链表里面添加数据
    public void addInit(){
        Scanner sc=new Scanner(System.in);
        System.out.println("2.该步骤执行初始化节点操作");
        System.out.println("a.请输入要插入节点的个数");

        int n=sc.nextInt();

        for(int i=0;i<n;i++){
            System.out.println("b.请输入要插入的元素的数值:");
            AnyType data=(AnyType)sc.next();
            if(beginMarker.next==null){
                Node<AnyType> node=new Node<AnyType>(data);
                beginMarker.next=node;
                node.prev=beginMarker;
                endMarker=node;
                endMarker.next=beginMarker;
                beginMarker.prev=endMarker;
            }
            else{
                Node<AnyType> node=new Node<AnyType>(data);
                endMarker.next=node;
                node.prev=endMarker;
                endMarker=node;
                endMarker.next=beginMarker;
                beginMarker.prev=endMarker;
            }
        }
    }
    // add 方法
    public void add(AnyType data){
        if(beginMarker.next==null){
            Node<AnyType> node=new Node<AnyType>(data);
            beginMarker.next=node;
            node.prev=beginMarker;
            endMarker=node;
            endMarker.next=beginMarker;
        }
        else{
            Node<AnyType> node=new Node<AnyType>(data);
            endMarker.next=node;
            node.prev=endMarker;
            endMarker=node;
            endMarker.next=beginMarker;
        }
    }

    public void add(){
        Scanner sc=new Scanner(System.in);
        System.out.println("3.该步骤/执行插入节点操作");
        System.out.print("*请输入要插入节点的个数*");
        System.out.println("(可用于插入第一个和最后一个节点)");
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            System.out.println("a.请输入要插入节点的位置:");
            int index=sc.nextInt();
            System.out.println("b.请输入要插入的元素的数值");
            AnyType data=(AnyType)sc.next();
            int j=0;
            if (beginMarker==null){
                Node<AnyType> Node = new Node<AnyType>(data);
                beginMarker.next=Node;
                Node.prev=beginMarker;
                endMarker=Node;
                endMarker.next=beginMarker;
            }
            else if(index==0){
                Node<AnyType> Node=new Node<AnyType>(data);
                Node<AnyType> temp=beginMarker.next;
                beginMarker.next=Node;
                Node.prev=beginMarker;
                Node.next=temp;
                temp.prev=Node;
            }
            else if(index>=size()){
                add(data);
            } else
            {
                Node<AnyType>Node=new Node<AnyType>(data);
                Node<AnyType> prior=beginMarker;
                while (j<index)
                {
                    j++;
                    prior=prior.next;
                }
                Node<AnyType> temp=prior.next;
                prior.next=Node;
                Node.prev=prior;
                Node.next=temp;
                temp.prev=Node;
            }
        }
    }
    public void remove() {
        int j=0;
        Scanner sc=new Scanner(System.in);
        System.out.println("4.该步骤执行删除节点操作");
        System.out.println("a.请输入要删除节点的个数:");
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            System.out.println("b.请输入要删除节点的位置:");
            int index=sc.nextInt();
            if (index<0||index>=size())
            {
                System.out.println("数组越界");

            } else if(index==0||size()==1) {
                if (size()==0){
                    beginMarker.next=null;
                    endMarker=null;
                } else {
                    Node<AnyType> fitst=beginMarker.next;
                    beginMarker.next=fitst.next;
                    fitst=null;
                }
            } else if(index==(size()-1)){
                if(size()==1)
                {
                    if (size()==0){
                        beginMarker.next=null;
                        endMarker=null;
                    } else {
                        Node<AnyType> fitst=beginMarker.next;
                        beginMarker.next=fitst.next;
                        fitst=null;
                    }
                }
                else{
                    Node<AnyType> pre=endMarker.prev;
                    pre.next=null;
                    endMarker=pre;
                    endMarker.next=beginMarker;
                    endMarker=null;
                }

            } else {
                Node<AnyType> prior=beginMarker.next;
                while(j<index){
                    j++;
                    prior=prior.next;
                }
                Node<AnyType> delete=prior;
                Node<AnyType> pre=delete.prev;
                Node<AnyType> after=delete.next;
                pre.next=delete.next;
                after.prev=pre;
                delete=null;
            }
        }
        System.out.println("**************");
    }

    //用于计算链表的大小
    public int size(){
        int size=0;
        Node<AnyType> node=beginMarker.next;
        while(node.data!=null) {
            size++;
            node=node.next;
        }
        return size;
    }
    //用于得到节点
    public Node<AnyType> getNode(int index) {
        int j=0;
        Node<AnyType> firstNode=beginMarker.next;
        if(index<0||index>=size())
        {
            System.out.println("数组越界");
        }
        while(j<index){
            j++;
            firstNode=firstNode.next;
        }

        return firstNode;
    }

    public void check(DoubleLinkedList list){
        System.out.println("5.是否执行逆置操作(是/否)?");
        Scanner sc=new Scanner(System.in);
        String str=sc.next();
        if(str.equals("是")){
            this.inverse(list);
        }
        else
            System.out.println("所有操作都已完成");
    }
    //实现链表的逆置操作
    public void inverse(DoubleLinkedList<AnyType> list1){
        System.out.println("逆置后的结果为:");
        int size=size();
        for(int i=size-1;i>=0;i--)
        {
            list1.add(this.getNode(i).data);
        }
        list1.print();
        System.out.println("所有操作都已结束");
    }
    //该方法用于输出链表中的所有数值
    public void print(){
        Node<AnyType> firstNode=beginMarker.next;
        if(firstNode==null){
            System.out.println("该链表为空");
        }
        else
        {
            while(firstNode.data!=null)
            {
                System.out.println(firstNode.data);
                firstNode=firstNode.next;
            }
        }
    }
    public static void main(String[] args) {
        DoubleLinkedList<Object> list=new DoubleLinkedList<Object>();
        list.init();
        DoubleLinkedList<Object> list1=new DoubleLinkedList<Object>();
        list.addInit();
        list.add();
        list.remove();
        list.check(list1);
        list.print();
    }
}
